/**
 * @author ChaP
 * @date 2019/05/20
 * @describe:
 */
package CodingTest.AC20190520;

/**
 * leetcode - 445
 * 给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。



 你可以假设除了数字 0 之外，这两个数字都不会以零开头。

 进阶:

 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

 示例:

 输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
 输出: 7 -> 8 -> 0 -> 7
 */

import java.util.ArrayList;
import java.util.List;

public class addTwoNumbers {
    class ListNode{
        int val;
        ListNode next;
        ListNode(int x){val = x;}
    }
//    public ListNode addTwoNumbers(ListNode l1,ListNode l2){
//        ListNode l11 = resver(l1);
//        ListNode l22 = resver(l2);
//        ListNode res = new ListNode(-1);
//        ListNode head = res;
//        int carry = 0,sum = 0,temp = 0;
//        while(l11 != null && l22!=null){
//             sum = l11.val+l22.val+carry;
//             temp = sum%10;
//            carry = sum/10;
//            res.next = new ListNode(temp);
//            res = res.next;
//            l11 = l11.next;
//            l22 = l22.next;
//        }
//        if(l11 == null){
//            sum = l22.val+carry;
//            temp = sum%10;
//            carry = sum/10;
//            res.next=new ListNode(temp);
//            res = res.next;
//            l22 = l22.next;
//        }
//        if(l22 == null){
//            sum = l11.val+carry;
//            temp = sum%10;
//            carry = sum/10;
//            res.next=new ListNode(temp);
//            res = res.next;
//            l11 = l11.next;
//        }
//        if(carry != 0){
//            res.next = new ListNode(carry);
//        }
//        head = resver(head.next);
//        return head;
//
//    }
//    public ListNode resver(ListNode listNode){
//        ListNode pReversedHead = null;
//        ListNode pNode = listNode;
//        ListNode pPrev = null;
//        while(pNode != null){
//            ListNode pNext = pNode.next;
//            if(pNext!=null){
//                pReversedHead = pNode;
//            }
//            pNode.next = pPrev;
//            pPrev = pNode;
//            pNode = pNext;
//        }
//        return pReversedHead;
//    }
    //方法一：倒置单链表 超时
    public ListNode addTwoNumbers(ListNode l1,ListNode l2){
        ListNode l11 = reverse(l1);
        ListNode l21 = reverse(l2);
        int carry = 0;
        ListNode res =null;
        ListNode head = res;
        int sum = 0;
        while(l11!=null && l21!=null){
            sum = l11.val+l21.val+carry;
            carry =sum/10;
            res.next = new ListNode(sum%10);
            res = res.next;
            l11 = l11.next;
            l21 = l21.next;
        }
        while(l11!=null){
            sum = carry+l11.val;
            carry = sum/10;
            res.next = new ListNode(sum%10);
            res = res.next;
            l11 = l11.next;
        }
        while(l21!=null){
            sum = carry+l21.val;
            carry = sum/10;
            res.next = new ListNode(sum%10);
            res = res.next;
            l11 = l21.next;
        }
        if(carry != 0)
            res.next = new ListNode(carry);
        ListNode head1 = reverse(head.next);
        return head1;

    }

    //优化倒置链表方法
    public ListNode addTwoNumbers1(ListNode l1,ListNode l2){
        ListNode l11 = reverse(l1);
        ListNode l21 = reverse(l2);
        ListNode head = new ListNode(0),p=head;
        int carry = 0;
        int sum = 0;
        while(l11 != null||l21!=null || carry!=0){
            ListNode t = new ListNode(0);
            t.val+=carry;
            if(l11 != null){
                t.val+=l11.val;
                l1 = l1.next;
            }
            if(l21!= null){
                t.val+=l21.val;
                l21 = l21.next;
            }
            carry = t.val/10;
            t.val = t.val%10;
            p.next = t;
            p=t;

        }
        if(head.next == null )return head;
        return reverse(head.next);
    }
    ListNode reverse(ListNode l){
        ListNode pre = null;
        ListNode now = l;
        ListNode next = null;
        ListNode result = null;
        while(now!=null){
            next = now.next; //保存节点的下一个节点
            if(next == null){
                result = now;
            }
            now.next = pre;
            pre = now;
            now = next;
        }
        return result;

    }

    //方法三：堆栈方法：
//    public ListNode addTwoNumbers1(ListNode l1,ListNode l2){
//
//    }


}
